﻿using System;
using System.Collections.Generic;

using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Windows.Devices.PointOfService;
using Windows.Foundation;
using 纸片人.PageViews;

namespace 纸片人
{
    public class Delaunay
    {
       static double epsilon = Math.Pow(2, -52);

        /// <summary>
        /// 
        /// </summary>
        /// <param name="vertices">顶点</param>
        public static List<Triangle> Delaunay1(List<Point> vertices)
        {


            int n;


            if ((n = vertices.Count) < 3)
            {
                return null;
            }
            List<int> indisces = new List<int>();

            for (int i = 0; i < n; i++)
            {
                indisces.Add(i);
            }



            //根据顶点的x坐标对索引进行降序排序 从大到小

            indisces.Sort((a, b) =>
 {

     return (int)vertices[b].X- (int)vertices[a].X ;
 }


            );

            var buffer = Supertriangle(vertices);
            vertices.Add(buffer[0]);
            vertices.Add(buffer[1]);
            vertices.Add(buffer[2]);
            //附加超级三角形以打开一个起始三角形
            List<Delaun> open = new List<Delaun>();
            List<Delaun> closed = new List<Delaun>();
          
            open.Add(Circumcircle(vertices, n + 0, n + 1, n + 2));

            int current = new int();
            //从顶点的最小x开始循环
            for (int i = indisces.Count - 1; i >= 0; i--)
            {
                current = indisces[i];
                int index = current;

                List<double> buffer1 = new List<double>();
                for (int j = open.Count - 1; j >= 0; j--)
                {

                    double dx = vertices[index].X - open[j].x;
                    if (dx > 0 && dx * dx > open[j].r)
                    {
                        closed.Add(open[j]);
                        open.RemoveAt(j);
                        continue;
                    }

                    double dy = vertices[index].Y - open[j].y;
                    if (dx * dx + dy * dy - open[j].r > epsilon)
                        continue;

                    buffer1.Add(open[j].i);
                    buffer1.Add(open[j].j);
                    buffer1.Add(open[j].j);
                    buffer1.Add(open[j].k);
                    buffer1.Add(open[j].k);
                    buffer1.Add(open[j].i);
                    open.RemoveAt(j);


                }

                Dedup(buffer1);
                for (int j = buffer1.Count; j > 0; )
                {

                    j--;

                   int i1  =(int)buffer1[j];
                    j--;
                   int i2  =(int)buffer1[j];


                    open.Add(Circumcircle(vertices,i1 , i2, index));
                }
            }

            for (int i = open.Count - 1; i >= 0; i--)
            {
                closed.Add(open[i]);
            }

            open.Clear();


            List<int> lin = new List<int>();
            for (int i = 0; i < closed.Count - 1; i++)
            {
                if (closed[i].i < n && closed[i].j < n && closed[i].k < n)
                {
                    lin.Add(closed[i].i);
                    lin.Add(closed[i].j);
                    lin.Add(closed[i].k);
                }
            }

           var lt = CreateTriangle(vertices, lin);
            return lt;
        }

        static List<Triangle> CreateTriangle(List<Point> v,List<int> p)
        {
            int[] indices = new int[6] { 0, 1, 1, 2, 2, 0 };

            List<Triangle> lt = new List<Triangle>();

            int count = p.Count - (p.Count % 3);

            for (int i = 0; i < count; i += 3)
            {
                Triangle t = new Triangle();

                for (int j = 0; j < 6; j += 2)
                {
                    var temp = p[i + indices[j]];
                    var item = p[i + indices[j + 1]];
                    TriangleSide ts = new TriangleSide();

                    ts.P0 = v[temp];
                    ts.P1 = v[item];
                    t.Side[j / 2] = ts;
                }

                lt.Add(t);
            }


            return lt;

        }



        public static Point[] Supertriangle(List<Point> v)
        {
            double xMin = double.PositiveInfinity;
            double yMin = xMin;
            double yMax = 0;
            double xMax = 0;
            double xl = 0;
            double yl = 0;
            double xlh = 0;
            foreach (var item in v)
            {
                if (item.X < xMin)
                {
                    xMin = item.X;
                }
                 if (item.X > xMax)
                {
                    xMax = item.X;
                }

                if (item.Y < yMin)
                {
                    yMin = item.Y;
                }
                 if (item.Y > yMax)
                {
                    yMax = item.Y;
                }

            }

            xl = xMax - xMin;
            yl = yMax - yMin;
            xlh = xl / 2;

            var buffer = new Point[3];

            buffer[0] = new Point((xMin - xlh - 2d), (yMax + 1d));
            buffer[1] = new Point((xMin + xlh), (yMin - yl));
            buffer[2] = new Point((xMax + xlh + 2d), (yMax + 1d));
            return buffer;

        }

        public static Delaun Circumcircle(List<Point> v, int i, int j, int k)
        {
            double x1 = v[i].X;
            double y1 = v[i].Y;
            double x2 = v[j].X;
            double y2 = v[j].Y;

            double x3 = v[k].X;
            double y3 = v[k].Y;

            double fabsy1y2 = Math.Abs(y1 - y2);
            double fabsy2y3 = Math.Abs(y2 - y3);


            double xc, yc, m1, m2, mx1, mx2, my1, my2, dx, dy;
            if (fabsy1y2 < epsilon)
            {
                m2 = -((x3 - x2) / (y3 - y2));
                mx2 = (x2 + x3) / 2.0;
                my2 = (y2 + y3) / 2.0;
                xc = (x2 + x1) / 2.0;
                yc = m2 * (xc - mx2) + my2;

            }
            else if (fabsy2y3 < epsilon)
            {
                m1 = -((x2 - x1) / (y2 - y1));
                mx1 = (x1 + x2) / 2.0;
                my1 = (y1 + y2) / 2.0;
                xc = (x3 + x2) / 2.0;
                yc = m1 * (xc - mx1) + my1;
            }
            else
            {
                m1 = -((x2 - x1) / (y2 - y1));
                m2 = -((x3 - x2) / (y3 - y2));
                mx1 = (x1 + x2) / 2.0;
                mx2 = (x2 + x3) / 2.0;
                my1 = (y1 + y2) / 2.0;
                my2 = (y2 + y3) / 2.0;
                xc = (m1 * mx1 - m2 * mx2 + my2 - my1) / (m1 - m2);
                yc = (fabsy1y2 > fabsy2y3) ?
               m1 * (xc - mx1) + my1 :
              m2 * (xc - mx2) + my2;
            }

            dx = x2 - xc;
            dy = y2 - yc;
            Delaun list = new Delaun(i, j, k, xc, yc, dx * dx + dy * dy);

            return list;



        }

        public static void Dedup(List<double> v)
        {
          
            double a, b, m, n;

            int count = 0;
            int cj = 0;
            int ci = 0;

            try
            {


                for (int j = v.Count; j > 0;)
                {


                    if (j - 1 >= v.Count)
                    {
                        j--;
                        cj = j;
                        b = double.NaN;
                        j--;
                        cj = j;
                        a = double.NaN;
                    }
                    else
                    {
                        j--;
                        cj = j;
                        b = v[j];
                        j--;
                        cj = j;
                        a = v[j];

                    }







                    for (int i = j; i > 0; )
                    {
                        

                        i--;
                        ci = i;
                        n= v[i];
                        
                        i--;
                        ci = i;
                        m = v[i];

                        

                        if ((a.Equals(m) && b.Equals(n)) || (a.Equals(n) && b.Equals(m)))
                        {
                        

                            if (j >= 0 && j < v.Count)
                            {
                                v.RemoveAt(j);

                            }
                            if (j >= 0 && j < v.Count)
                            {
                                v.RemoveAt(j);

                            }

                            if (i >= 0 && i < v.Count)
                            {
                                v.RemoveAt(i);

                            }
                            if (i >= 0 && i < v.Count)
                            {
                                v.RemoveAt(i);

                            }
                            break;
                        }
                        else if(double.IsNaN(a) || double.IsNaN(b))
                        {
                            break;
                        }
                    }

                }


            }
            catch(Exception ex)
            {
                 count = 0;
                 cj = 0;
                 ci = 0;
            }
        }
    }

    public class Delaun
    {
        public int i { get; set; }
        public int j { get; set; }
        public int k { get; set; }
        public double x { get; set; }
        public double y { get; set; }
        public double r { get; set; }

        public Delaun(int i, int j, int k, double x, double y, double r)
        {
            this.i = i;
            this.j = j;
            this.k = k;
            this.x = x;
            this.y = y;
            this.r = r;
        }
    }
}
public class Triangle
{
    public TriangleSide[] Side { get; set; } = new TriangleSide[3];
}

public class TriangleSide
{
    public Point P0 { get; set; }
    public Point P1 { get; set; }
}